package srv;

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import model.DFA;
import model.DFAEdge;
import model.DFANode;
import model.NFA;
import model.Node;
import model.TerminalNode;

/***
 * PRE - > NFA && NFA - > DFA
 * 
 * @author LD
 *
 */
class NFAfunc {
	private NFA nfa = new NFA();

	// 将正规表达式串r1(以'#'作为结束标记)转换为存于r2后缀表达式
	public String change(String r1) {
		StringBuffer res = new StringBuffer();
		Stack<Character> opStack = new Stack<Character>();// 用于暂存运算符的栈
		opStack.push('#'); // 将‘#’压入栈底
		int i = 0; // 指示r1中字符位置
		char ch;
		ch = r1.length() >= i ? r1.charAt(i) : ' ';

		while (ch != '#') {// 顺序处理中缀表达式中的每个字符
			if (ch == ' ')
				ch = r1.length() >= ++i ? r1.charAt(i) : ' ';// 对空格字符不做处理，顺序读取下一个字符
			else if (ch == '(') {
				opStack.push(ch);// 左括号直接压入栈中
				ch = r1.length() >= ++i ? r1.charAt(i) : ' ';
			} else if (ch == ')') {// 对右括号，使括号内运算符依次出栈，并写入r2中
				while (opStack.lastElement() != '(') {
					res.append(opStack.lastElement());
					opStack.pop();
				}
				opStack.pop();
				ch = r1.length() >= ++i ? r1.charAt(i) : ' ';
			} else if (ch == '.' || ch == '|' || ch == '*') {
				char w = opStack.lastElement();
				while (priority(w) >= priority(ch)) {// 若栈顶算符优先级大于当前算符优先级，弹出输出到r2
					res.append(w);
					opStack.pop();
					w = opStack.lastElement();
				}
				opStack.push(ch);// 将当前的算符压入栈中
				ch = r1.length() >= ++i ? r1.charAt(i) : ' ';
			} else {
				res.append(ch);
				ch = r1.length() >= ++i ? r1.charAt(i) : ' ';
			}
		}

		ch = opStack.lastElement();
		while (ch != '#') // 将栈中的元素全部弹出
		{
			res.append(opStack.lastElement());
			opStack.pop();
			ch = opStack.lastElement();
		}
		opStack.pop();
		res.append("$");// 结束r2
		return res.toString();
	}

	NFA reToNFA(String r2) {
		Stack<NFA> nfaStack = new Stack<NFA>(); // 定义暂存中间的生成的NFA栈
		int i = 0; // 用于指示扫描r2串的字符的位置

		char ch;
		ch = r2.length() >= ++i ? r2.charAt(i) : ' ';// ch保存R2中扫描到的字符

		while (ch != '$') {// 顺序处理后缀表达式的每个字符
			if (isletter(ch)) {// 对于字母表中的元素，作如下处理
				nfa.setNodenum(nfa.getNodenum() + 1);
				Node s1 = new Node(nfa.getNodenum()); // create a new Node,its
														// label is ++Nodenum
				nfa.setNodenum(nfa.getNodenum() + 1);
				Node s2 = new Node(nfa.getNodenum()); // create a new Node,its
														// label is ++Nodenum
				s1.setAcceptstatetag(0);// s1为非接受态
				s1.getFirstEdge().setSymbol(ch);
				s1.getFirstEdge().setNextNode(s2);// s1通过 a边连接到s2
				s1.getLastEdge().setNextNode(null);// s1无其他发出边

				s2.setAcceptstatetag(1);// s2为接受态
				s2.getFirstEdge().setNextNode(null);// s2无发出边
				s2.getLastEdge().setNextNode(null);

				// this->nfaNodes.push_back(*s1);//将新生成的结点插入到结点集合中
				// this->nfaNodes.push_back(*s2);

				// this->start=s1;
				// this->end=s2;

				NFA tempNFA = new NFA();
				tempNFA.setStart(s1);
				tempNFA.setEnd(s2);
				tempNFA.setNodenum(nfa.getNodenum());

				nfaStack.push(tempNFA);// 将新生成的NFA压入栈 中

				ch = r2.length() >= ++i ? r2.charAt(i) : ' ';// 顺序读取下一个字符

			} else if (ch == '.') {// 对于'&',先从栈中弹出两个NFA，将其合并，然后压入栈中

				// 从栈中弹出两个NFA，分别存于R1和R2中
				NFA R2 = nfaStack.lastElement();
				nfaStack.pop();

				NFA R1 = nfaStack.lastElement();
				nfaStack.pop();

				// 将R1和R2合并，合并后的NFA为R1
				R1.getEnd().getFirstEdge().setSymbol('@');
				R1.getEnd().getFirstEdge().setNextNode(R2.getStart());
				R1.getEnd().getLastEdge().setSymbol('\0');

				R1.getEnd().setAcceptstatetag(0);// R1的接受态设为非接受态

				// start=R1->start;
				// end=R2->end;
				R1.setEnd(R2.getEnd());

				R1.setNodenum(nfa.getNodenum());// 保存当前结点的数目

				nfaStack.push(R1);// 将合并后的NFA压入栈中
				ch = r2.length() >= ++i ? r2.charAt(i) : ' ';
			} else if (ch == '|') {
				NFA R2 = nfaStack.lastElement();
				nfaStack.pop(); // '@'

				NFA R1 = nfaStack.lastElement();
				nfaStack.pop();

				nfa.setNodenum(nfa.getNodenum() + 1);
				Node s3 = new Node(nfa.getNodenum()); // create a new Node,its
														// label is ++Nodenum
				nfa.setNodenum(nfa.getNodenum() + 1);
				Node s4 = new Node(nfa.getNodenum());
				s3.setAcceptstatetag(0);
				s3.setAcceptstatetag('@');
				s3.getFirstEdge().setNextNode(R1.getStart());

				s3.getLastEdge().setSymbol('@');
				s3.getLastEdge().setNextNode(R2.getStart());

				s4.setAcceptstatetag(1);

				R1.getEnd().getFirstEdge().setSymbol('@');
				R1.getEnd().getFirstEdge().setNextNode(s4);
				R1.getEnd().getLastEdge().setNextNode(null);
				R1.getEnd().setAcceptstatetag(0);

				R2.getEnd().getFirstEdge().setSymbol('@');
				R2.getEnd().getFirstEdge().setNextNode(s4);
				R2.getEnd().getLastEdge().setNextNode(null);
				R2.getEnd().setAcceptstatetag(0);// 置R2->end为非接受态

				NFA tempNFA = new NFA();
				tempNFA.setStart(s3);
				tempNFA.setEnd(s4);
				tempNFA.setNodenum(nfa.getNodenum());
				nfaStack.push(tempNFA);
				ch = r2.length() >= ++i ? r2.charAt(i) : ' ';
			} else if (ch == '*') {
				NFA R1 = nfaStack.lastElement();
				nfaStack.pop();
				nfa.setNodenum(nfa.getNodenum() + 1);
				Node s3 = new Node(nfa.getNodenum()); // create a new Node,its
														// label is ++Nodenum
				nfa.setNodenum(nfa.getNodenum() + 1);
				Node s4 = new Node(nfa.getNodenum());
				s3.setAcceptstatetag(0);
				s3.getFirstEdge().setSymbol('@');
				s3.getFirstEdge().setNextNode(R1.getStart());

				s3.getLastEdge().setSymbol('@');
				s3.getLastEdge().setNextNode(s4);
				s4.setAcceptstatetag(1);// s4设为接受态
				R1.getEnd().getFirstEdge().setSymbol('@');
				R1.getEnd().getFirstEdge().setNextNode(s4);
				R1.getEnd().getLastEdge().setSymbol('@');
				R1.getEnd().getLastEdge().setNextNode(R1.getStart());
				R1.getEnd().setAcceptstatetag(0);
				R1.setStart(s3);
				R1.setEnd(s4);
				R1.setNodenum(nfa.getNodenum());
				nfaStack.push(R1);

				ch = r2.length() >= ++i ? r2.charAt(i) : ' ';

			} else
				error();
		}

		NFA nfa = new NFA();
		nfa = nfaStack.lastElement();
		// this->end=nfa->end;
		// this->start=nfa->start;
		nfaStack.pop();
		return nfa;
	}

	void join(NFA nfa1) {
		if (nfa.getStart() == null)
			nfa.setStart(nfa1.getStart());
		else {
			nfa.setNodenum(nfa.getNodenum() + 1);
			Node s3 = new Node(nfa.getNodenum());
			s3.setAcceptstatetag(0);
			s3.getFirstEdge().setSymbol('@');
			s3.getFirstEdge().setNextNode(nfa.getStart());// 第一条边指向第一个NFA的开始处
			s3.getLastEdge().setSymbol('@');
			s3.getLastEdge().setNextNode(nfa.getStart());// 第二条边指向第二个NFA的开始处
			nfa.setStart(s3);
		}
	}

	boolean isletter(String c) {
		String ptr = c;
		if (isletter(ptr.charAt(0)))
			return true;
		else
			return false;
	}

	boolean isletter(char c) {
		if (isalnum(c))
			return true;

		switch (c) {
		case '+':
			return true;
		case '-':
			return true;
		case '/':
			return true;
		case '=':
			return true;
		default:
			return false;
		}
	}

	private boolean isalnum(char c) {
		if (c >= '0' && c <= '9')
			return true;
		return false;
	}

	char strToChar(String str) {
		return str.charAt(0);
	}

	int priority(char c) {
		switch (c) {
		case '#':
			return 0;
		case '|':
			return 1;
		case '.':
			return 2;
		case '*':
			return 3;
		default:
			error();
			return -1;
		}
	}

	// void asign(NFA nfa)
	// {
	// nfa.end=end;
	// nfa.nfaNodes=nfaNodes;
	// nfa.Nodenum=Nodenum;
	// nfa.start=start;
	// }

	/****
	 * // 对正规表达式预处理
	 * 
	 * @param r1
	 * @return
	 */
	private String preProcess(String r1) {
		StringBuffer re = new StringBuffer(r1);
		re.append("#");
		int size = re.length();
		char[] ptr = new char[2 * size];
		int j = 0;// 用于指示暂存队列的游标
		// vector<char> temp;//暂存插入后的结果
		char cur = 0;// 存当前取得的字符
		char next = 0;// 当前字符的下一个字符

		for (int i = 0; i < size - 1; i++) {
			cur = re.charAt(i);
			next = re.charAt(i + 1);
			ptr[j++] = cur;
			if (isletter(cur) && isletter(next))// 若当前和下一个字符都是字母、数字或运算符，ze插入'.'
				// temp.push_back('.');
				ptr[j++] = '.';
			if (cur == ')' && next == '(')
				ptr[j++] = '.';
		}
		// temp.push_back(next);
		// re.empty();
		ptr[j] = next;
		re = new StringBuffer();// 清空当前正规表达式
		int index = 0;
		cur = ptr[index];
		char temp;
		while (cur != '#')// 将处理后的正规表达式赋给re
		{
			temp = cur;
			re.append(temp);
			cur = ptr[++index];
		}

		re.append("#");
		return re.toString();
	}

	/****
	 * 开始转换表 入口函数
	 * 
	 * @param reTable
	 * @param actionTable
	 */
	public void convrtAll(Map<String, String> reTable,
			Map<String, String> actionTable) {
		String infix;// 存中缀表达式
		String suffix;// 存后缀表达式
		TerminalNode endNode = new TerminalNode();// 暂存终止结点
		NFA tempNFA = new NFA();// 暂存从正规表达式转换而来的NFA
		nfa.setStart(null);
		nfa.setEnd(null);
		String str;
		// 获取map集合中的所有键的Set集合
		Set<String> reKeySet = reTable.keySet();
		// 有了Set集合就可以获取其迭代器，取值
		Iterator<String> iter = reKeySet.iterator();
		while (iter.hasNext()) {
			str = iter.next();
			String s = actionTable.get(str);
			System.out.println("s = " + s);

			if (reTable.containsKey(str))// 如果actionTable当前元素在reTable中，从reTable中取出相应的正规表达式
				infix = reTable.get(str);
			else
				infix = str; // 否则，取出当前actionTable的第一项

			infix = preProcess(infix);// 在正规表达式中插入连接运算符‘.’
			suffix = change(infix);// 将中缀表达式转为后缀表达式
			tempNFA = reToNFA(suffix);// 将后缀表达式转换为NFA存入tempNFA中

			endNode.setId(tempNFA.getEnd().getLabel());// 保存终止结点编号
			endNode.setType(iter.toString());// 保存终止结点类型

			nfa.addTerminalNode(endNode);
			join(tempNFA);

		}
		getCharSet(reTable, actionTable);// 获得输入字符集
	}

	/**
	 * print nfa
	 */
	void printTer() {
		for (int i = 0; i < nfa.getTerminalNode().size(); i++) {
			System.out.println(nfa.getTerminalNode().get(i));
		}
	}

	void preOrder(Node tree) {
		Node left = null;
		Node right = null;
		if (tree != null) {
			nfa.getNfaNodes().add(tree);
			left = tree.getFirstEdge().getNextNode();
			right = tree.getLastEdge().getNextNode();
			if (left != null)
				preOrder(left);
			if (right != null)
				preOrder(right);
		}
		return;
	}

	void preOrder(Node tree, DFA dfa)// 采用广度优先算法遍历NFA的结点，将其存储到DFA结点表中
	{
		int n = nfa.getNodenum() + 1;// 取结点个数
		int w = 0;
		Node neighbor = null;
		boolean visited[] = new boolean[n];
		for (int i = 0; i < n; i++)
			visited[i] = false;
		int loc = tree.getLabel();
		nfa.getNfaNodes().add(tree);
		System.out.println("label:" + loc);
		visited[loc] = true;
		Stack<Node> que = new Stack<Node>();
		que.push(tree);
		while (!que.empty()) {
			Node top = que.lastElement();
			que.pop();
			neighbor = top.getFirstEdge().getNextNode();

			if (neighbor != null)// 判断第一条边是否为空
			{
				w = neighbor.getLabel();
				if (visited[w] == false)// 若未访问过
				{
					nfa.getNfaNodes().add(neighbor);// 压结点地址入栈
					loc = neighbor.getLabel();
					// cout<<"label : "<<loc<<endl;//访问该节点
					que.push(neighbor);
					visited[w] = true;
				}// 第一条边访问结束
				neighbor = top.getLastEdge().getNextNode();
				if (neighbor != null)// 若第二条边不为空
				{
					w = neighbor.getLabel();
					if (visited[w] == false)// 若未访问过
					{
						nfa.getNfaNodes().add(neighbor);// 压结点地址入栈
						loc = neighbor.getLabel();
						// cout<<"label : "<<loc<<endl;//访问该节点
						que.push(neighbor);
						visited[w] = true;
					}
				}// 第二条边访问结束
			}
		}
	}

	void nfaTodfa(DFA dfa)// 将NFA的结点集赋给DFA
	{

		dfa.setStart(nfa.getStart().getLabel());
		Node ptr = nfa.getStart();
		nfa.getNfaNodes().clear();
		preOrder(ptr, dfa);
		DFANode tempNode = new DFANode();
		System.out.println("NFA 的结点未排序前:");

		// 下面是将nfa的节点表存储至dfa的结点表
		for (int it = 0; it < nfa.getNfaNodes().size(); it++) {
			// cout<<"label"<<'\t'<<(*it)->label<<endl;
			Node tempN = nfa.getNfaNodes().get(it);
			tempNode.setAcceptstatetag(tempN.getAcceptstatetag());
			tempNode.setLabel(tempN.getLabel());

			// cout<<"LABEL----"<<tempNode->label
			// <<"\tTER------"<<tempNode->acceptstatetag<<endl;

			// 存储结点发出边
			if (tempN.getFirstEdge() != null) {
				DFAEdge edge = new DFAEdge();
				edge.setSymbol(tempN.getFirstEdge().getSymbol());
				edge.setNextNode(tempN.getFirstEdge().getNextNode().getLabel());

				// cout<<"第一结点："<<edge.nextNode<<'\t';

				tempNode.getEdges().add(edge);
				if (tempN.getLastEdge().getNextNode() != null) {
					edge.setSymbol(tempN.getLastEdge().getSymbol());
					edge.setNextNode(tempN.getLastEdge().getNextNode()
							.getLabel());

					// cout<<"第二结点："<<edge.nextNode<<'\n';

					tempNode.getEdges().add(edge);
				}
			}// 存储结点边部分结束

			// cout<<endl;

			dfa.getDfaNodeTable().add(tempNode);
			tempNode.getEdges().clear();
		}

		dfa.setCharSet(nfa.getCharSet());// 将NFA字母表赋给DFA

		dfa.sortNodes();// 将结点按id排序，下号标即为结点id号
		dfa.setAcceptedNode(nfa.getTerminalNode());
		// Vector<TerminalNode>::iterator iter2;

		for (int i = 0; i < nfa.getTerminalNode().size(); i++) {
			/***********************************
			 * 有问题
			 */
			dfa.getTerminal().get(nfa.getTerminalNode().get(i).getId())
					.equals(nfa.getTerminalNode().get(i).getType());
		}
		// dfa.printNode();
		// dfa.epslonClosure(14);
	}

	//
	void getCharSet(Map<String, String> reTable, Map<String, String> reaction) {
		// 获取map集合中的所有键的Set集合
		Set<String> reKeySet = reTable.keySet();
		// 有了Set集合就可以获取其迭代器，取值
		Iterator<String> iter = reKeySet.iterator();
		String temp;// 暂存字符串
		while (iter.hasNext()) {
			temp = iter.next();
			char ch = 0;
			for (int i = 0; i < temp.length(); i++) {
				ch = temp.charAt(i);
				if (isletter(ch))
					nfa.getCharSet().add(ch);
			}
		}
		// 获取map集合中的所有键的Set集合
		Set<String> acKeySet = reaction.keySet();
		// 有了Set集合就可以获取其迭代器，取值
		Iterator<String> iter1 = acKeySet.iterator();
		while (iter1.hasNext()) {
			// cout<<iter->first<<" "<<iter->second<<endl;
			temp = iter1.next();
			char ch = ' ';
			for (int i = 0; i < temp.length(); i++) {
				ch = temp.charAt(i);
				if (isletter(ch))
					nfa.getCharSet().add(ch);
			}
		}
		// //std::ostream_iterator<char> output(cout," ");
		// //cout<<"charSet contain "<<endl;
		// //std::copy(charSet.begin(),charSet.end(),output);
	}

	private void error() {
		// TODO Auto-generated method stub
		System.out.println("Error!");
	}

}